class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        // dp[i][j]表示从当前位置出发，到达终点的最低初始健康点数
        // dp[i][j]依赖于右边的格子和下边的格子
        // 以右边的格子为例，比如dp[i][j + 1]根据状态的定义就是从[i, j + 1]位置出发，到达终点的最低初始健康点数
        // 所以当前格子[i, j]的最低初始点数设为dp[i][j]的话，那么dp[i][j]+dungeon[i][j]必须>=dp[i][j + 1]，即dp[i][j] = dp[i][j + 1]-dungeon[i][j]
        // 如果dungeon[i][j]是一个正数，则说明这是一个血包，计算完dp[i][j]会是一个负数
        // 说明从当前这个位置出发，而且是负血量就可以到达终点，但这是不符合逻辑的啊，必须至少一滴血你才能享受到这里的血包
        // 所以计算完之后dp[i][j] = max(1, dp[i][j])
        // 往下走的格子同上述分析

        int m = dungeon.size(), n = dungeon[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        
        // 初始化，保证填表的时候不越界
        dp[m][n - 1] = 1;

        // 根据状态定义，此时遍历顺序就得从最后一个位置往前推导了
        for(int i = m - 1; i >= 0; i--)
        {
            for(int j = n - 1; j >= 0; j--)
            {
                dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
                dp[i][j] = max(1, dp[i][j]);
            }
        }
        return dp[0][0];
    }
};